class Solution {
public:
    vector<string> rst;
    map<char, vector<char>> keys = {
        {'2', {'a', 'b', 'c'}},
        {'3', {'d', 'e', 'f'}},
        {'4', {'g', 'h', 'i'}},
        {'5', {'j', 'k', 'l'}},
        {'6', {'m', 'n', 'o'}},
        {'7', {'p', 'q', 'r', 's'}},
        {'8', {'t', 'u', 'v'}},
        {'9', {'w', 'x', 'y', 'z'}}
    };
    vector<string> letterCombinations(string digits) {
        if(digits == "") return rst;
        string alphabets = "";
        letterCombinationsStep(digits, alphabets);
        return rst;
    }

    void letterCombinationsStep(string &digits, string &alphabets) {
        if(digits.length() == alphabets.length()){
            rst.push_back(alphabets);
            return;
        }

        char digit = digits[alphabets.length()];
        for(char alphabet : keys.find(digit)->second) {
            alphabets.push_back(alphabet);
            letterCombinationsStep(digits, alphabets);
            alphabets.pop_back();
        }
    }
};